// m

// 给定一个二叉树，返回其节点值的锯齿形层序遍历
// 锯齿形层序遍历：从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

// 解题思路： 广度优先搜索，在二叉树的层序遍历的基础上需要增加些变化
// 普通的广度优先搜索只取一个元素，变化后的广度优先搜索每次取第i层上所有的元素
// 新增一个odd变量，用于判断当前层数是奇数还是偶数层，从而判断元素遍历方向
// 存储每层元素的level列表改用双端队列，如果是奇数层，则末尾添加元素，如果是偶数层，则从头部添加元素

// 具体步骤如下：
// 根节点入队
// 当队列不为空时，求出当前队列长度S，并判断当前层数的奇偶性
// 依次从队列中取出这个S个元素
//    如果是奇数层，则从level末尾添加元素
//    如果是偶数层，则从level头部添加元素
// 然后保存将其左右子节点入队，然后继续迭代
// 当队列为空时，结束
const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};
function zigzagLevelOrder(root) {
    if (!root) {
        return []
    }
    let queue = [root]
    let order = []
    let odd = true
    while (queue.length) {
        let level = []
        let size = queue.length
        for (let i = 0; i < size; i++) {
            let curr = queue.shift()
            if (odd) {
                level.push(curr.val)
            } else {
                level.unshift(curr.val)
            }
            if (curr.left) {
                queue.push(curr.left)
            }
            if (curr.right) {
                queue.push(curr.right)
            }
        }
        if (level.length) {
            order.push(level)
        }
        odd = !odd
    }
    return order
}

console.log(zigzagLevelOrder(root))

